package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html
https://leetcode.cn/problems/subsets-ii/description/

90. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。


示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：
输入：nums = [0]
输出：[[],[0]]
 */
class leetcode_90 {
    @Test
    fun test_1() {
        val actual = subsetsWithDup(intArrayOf(1, 2, 2))
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(
            arrayListOf(), arrayListOf(1), arrayListOf(1, 2), arrayListOf(1, 2, 2), arrayListOf(2), arrayListOf(2, 2)
        )
        Assert.assertEquals(actual.toString(), expect.toString())
    }

    @Test
    fun test_2() {
        val actual = subsetsWithDup(intArrayOf(0))
        val expect: ArrayList<ArrayList<Int>> = arrayListOf(
            arrayListOf(), arrayListOf(0)
        )
        Assert.assertEquals(actual.toString(), expect.toString())
    }

    fun subsetsWithDup(nums: IntArray): List<List<Int>> {

        /*
        回溯法
        1 排序, 树层去重
        2 子集 - 收集所有节点
         */
        val path: ArrayList<Int> = ArrayList<Int>()
        val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
        val used: BooleanArray = BooleanArray(nums.size)
        nums.sort()
        backtracking(nums, 0, path, result, used)
        return result
    }


    private fun backtracking(nums: IntArray, startIndex: Int, path: ArrayList<Int>, result: ArrayList<ArrayList<Int>>, used: BooleanArray) {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        // 结束条件
        if (startIndex > nums.size) {
            return
        }
        // 收集结果
        val temp: ArrayList<Int> = ArrayList<Int>()
        temp.addAll(path)
        result.add(temp)

        // 3 确定单层递归的处理逻辑
        for (i in startIndex until nums.size) {   // [startIndex, end index]
            // 处理节点
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { // 树层去重
                continue
            }
            path.add(nums[i])
            used[i] = true

            // 递归
            backtracking(nums, i + 1, path, result, used)

            // 回溯
            path.removeAt(path.size - 1)
            used[i] = false

            // 去重？剪枝？
        }
    }
}